This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 11-273219, filed Sep. 27, 1999, the entire contents of which are incorporated herein by reference.
This invention relates to a queue control device and a queue control method which are applied to, for example, ATM (Asynchronous Transfer Mode) communications and computers.
FIG. 7 shows a conventional queue management method. The queue management method includes a pointer table 101 having an n number of addresses and a storage area 102 that stores the head address and tail address for the queue in the pointer table 101. When a queue is constructed for an n number of elements, address A0 to address An are allocated to the individual elements in the pointer table 101. In each address in the pointer table 101, pointer information indicating the next element for constituting the queue is stored. The storage area 102 stores the head address and tail address. The head address indicates the head element in the queue in the pointer table 101 and the tail address indicates the tail element. Using these addresses, the queue is managed.
For example, in the example of FIG. 7, address A0 in the pointer table has been stored in the head address in the storage area 102 and address A7 has been stored in the tail address. In address A0 in the pointer table 101 indicated by the head address, pointer information A2 indicating the address for the next element has been stored. Furthermore, pointer information A8 indicating the address for the next element has been stored in address A2 in the pointer table 101 and pointer information A7 indicating the tail address is stored in address A8 in the pointer table 101. Since address A7 in the pointer table 101 is the tail address, it has not next pointer information and have 0 indicating the end of the queue stored in it. In this way, a queue consisting of addresses A0xe2x86x92A2xe2x86x92A8xe2x86x92A7 is constructed.
The queue is accessed sequentially, starting at address A0. After the process corresponding to address A0 has been completed, the pointer information corresponding to address A0 is deleted from the queue and the head address is updated from A0 to A2.
There are two methods of adding new elements to the queue as follows. When element Ai is added to an FIFO (First In First Out) queue, pointer information indicating Ai is stored in the tail address A7 of the pointer table 101 and the tail address of the storage area 102 is updated from A7 to Ai. On the other hand, when element Ai is added to an LIFO (Last In First Out) queue, pointer information indicating the head address A0 is stored in Ai of the table 101 and the head address of the storage area 102 is updated from A0 to Ai.
FIG. 8 shows a queue management method for managing two types of queues. To manage a first and a second queue, two storage areas 111, 112 are provided. The storage area 111 holds the head address 1 and tail address 1 in the first queue. The first queue is managed using the head address 1 and tail address 1. The storage area 112 holds the head address 2 and tail address 2 in the second queue. The second queue is managed using the head address 2 and tail address 2.
Now, consider a case where queues are managed in a communication control system with, for example, an n number of communication channels. For example, in ATM communications, virtual channels are shared on one physical line, and packet is changed into ATM cell and transmits in the virtual channel. A bandwidth used by each virtual channel is classified into some groups corresponding to the application of each virtual channel, and each group is controlled according to a priority. That is, channels of each group are managed by the queue and each group is controlled according to the priority.
FIG. 9 shows the queue management method. In FIG. 9, a time table is provided in a storage area 121. The time table has an m number of time entries T0 to Tm. Each channel is serviced in this order of T0 to Tm of the m number of entries. In each of the time entries T0 to Tm, the head address and tail address of a queue for a virtual channel serviceable at each time have been stored. For example, at time entry T0, Ah1-0 (=A0) has been stored in the head address and At1-0 (=A2) has been stored in the tail address. Moreover, at time entry T1, Ah1-1 (=A3) has been stored in the head address and At1-1 (=A3) has been stored in the tail address.
On the other hand, according to the head address and tail address at each of the entries, the pointer indicating the next element and information indicating the end have been stored in the pointer table 122.
Each channel is served in order from time entry T0 in the time table. After service has been given at time entry Tm, service is given, starting at time entry T0 again. After the virtual channel registered in a certain entry has been given service, the virtual channel is registered in another time entry. If another virtual channel has been registered in that time entry, the virtual entry will constitute a queue at that time entry.
Consider a case where two types of virtual channels differing in priority are controlled in such a communication control device. As shown in FIG. 9, when there is only one queue at time entries T0 to Tm, control can be performed only by FIFO or LIFO. This causes a problem: the two types of virtual channels cannot be controlled independently on the basis of their priority.
To overcome this problem, as shown in FIG. 10, a queue control method having two sets of head addresses and tail addresses for each of the time entries T0 to Tm is needed. The method is based on the method shown in FIG. 8. In the example shown in FIG. 10, there are a first queue and a second queue for each of the time entries T0 to Tm. With the first queue and second queue, two types of virtual channels differing in priority can be controlled as shown in the pointer table 122. Specifically, for example, at time entry T0, the first queue specified by the head address Ah1-0 (=A0) and tail address At1-0 (=A2) is processed. Then, the second queue specified by the head address Ah2-0 (=A1) and tail address At2-0 (=A5) is processed.
As shown in FIG. 10, however, when two types of queues composed of the first queue and second queue are managed using the m number of time entries T0 to Tm, the storage area 123 requires an area for storing 4xc3x97m head addresses and tail addresses. This leads to a problem: the storage capacity of the storage area 123 increases.
It is, accordingly, an object of the present invention to overcome the above problem by providing a queue control device and a queue control method which are capable of preventing the storage capacity from increasing by controlling a plurality of queues as a single queue.
The foregoing object is accomplished by providing a queue control device comprising: a first storage area for storing a first and a second queue, the first queue including a plurality of elements, each of the elements having an address specifying the next element, and the second queue including a plurality of elements, each of the elements having an address specifying the next element; a second storage area for storing first pointer information and second pointer information, the first pointer information being a head address specifying the head element in the first queue, and the second pointer information being a tail address specifying the tail element in the second queue; and a controller which controls the first and second storage areas and which sets not only an address specifying the head element in the second queue in the tail element in the first queue stored in the first storage area but also an address specifying the tail address in the first queue in the tail element in the second queue and controls the first and second queues according to the first pointer information and second pointer information stored in the second storage area.
The foregoing object is further accomplished by providing a queue control method including a first queue composed of a plurality of elements, each of the elements having an address specifying the next element, and a second queue composed of a plurality of elements, each of the elements having an address specifying the next element, the queue control method comprising the steps of: setting an address specifying the head element in the second queue in the tail element in the first queue; setting an address specifying the tail element in the first queue in the tail element in the second queue; processing the first and second queues on the basis of first pointer information made up of the head address in the first queue and second pointer information made up of the tail address in the second queue.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out hereinafter.